// 给定一个链表，如何判断链表中是否有环？
// 思路分析：

// 1. 首先创建两个指针 1 和 2，同时指向这个链表的头节点。
//    然后开始一个大循环，在循环体中，让指针 1 每次向下移动一个节点，让指针 2 每次向下移动两个节点，
//   然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
// 2. 例如链表 A->B->C->D->B->C->D，两个指针最初都指向节点 A，进入第一轮循环，指针 1 移动到了节点 B，
//  指针 2 移动到了 C。第二轮循环，指针 1 移动到了节点 C，指针 2 移动到了节点 B。
//  第三轮循环，指针 1 移动到了节点 D，指针 2 移动到了节点 D，此时两指针指向同一节点，判断出链表有环。
// 3. 假设从链表头节点到入环点的距离是 D，链表的环长是 S。那么循环会进行 S 次，可以简单理解为 O（N）。
//  除了两个指针以外，没有使用任何额外存储空间，所以空间复杂度是 O（1）。

const Node = function (data) {
  this.data = data;
  this.next = null;
};

const nodeA = new Node("A");
const nodeB = new Node("B");
const nodeC = new Node("C");
const nodeD = new Node("D");
const nodeE = new Node("E");
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeC;
// 解法1
function isCircularLinkedList(head) {
  if (head === null || head.next === null) {
    return false;
  }
  let point1 = head;
  let point2 = head;
  do {
    point1 = point1.next;
    point2 = point2.next && point2.next.next;
  } while (point1 && point2 && point1 !== point2);
  if (point1 === point2) {
    return true;
  }
  return false;
}

// 解法2
function isCircularLinkedList2(head) {
  // 只要结点存在，那么就继续遍历
  while (head) {
    // 如果 flag 已经立过了，那么说明环存在
    if (head.flag) {
      return true;
    } else {
      // 如果 flag 没立过，就立一个 flag 再往下走
      head.flag = true;
      head = head.next;
    }
  }
  return false;
}
// console.log(isCircularLinkedList(nodeA));
console.log(isCircularLinkedList2(nodeA));

// 真题描述：给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
// 解法1
const detectCycle = function (head) {
  while (head) {
    if (head.flag) {
      return head;
    } else {
      head.flag = true;
      head = head.next;
    }
  }
  return null;
};

// 解法2
console.log(detectCycle(nodeA));